package leecode;

/**
 * 功能描述：剪绳子问题2  需要取模
 *
 * @Author: lwg
 * @Date: 2021/4/27 14:57
 */
public class demo15 {

    public static int cuttingRope(int n) {

        if (n < 4) {
            return n - 1;    //需要有一个长度为1的绳子(题目中要求n>1)
        }
        long product = 1;//乘积初始值
        while (n > 4) {
            product = product * 3 % 1000000007;
            n -= 3;
        }
        return (int) (product * n % 1000000007);  //当n=4时1*4=4;  n>4时上述连续乘积得到的新值*n(不停-3后剩下的n中的最大值4=2*2)
    }

    public static void main(String[] args) {
        System.out.println(cuttingRope(120));
    }

    /*public static int cuttingRope(int n) {
        int[] dp = new int[n + 1];
        if (n < 4) {
            dp[n] = n - 1;
        }
        for (int i = 4; i < n + 1; i++) {
            int max = 0;
            for (int j=2;j<i;j++){
                max=Math.max(max,Math.max(j*(i-j),j*dp[i-j]));
            }
            dp[i]=max;

        }
        return (int)(dp[n]&1000000007);
    }

    public static void main(String[] args) {
        System.out.println(cuttingRope(10));
    }*/
}
